package leetcode;

/**
 * 动态规划：回文子串
 */
public class Solution69 {
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        //创建dp数组
        boolean[][] dp  = new boolean[len][len];
        int result = 0;
        //for循环遍历
        for(int i = len - 1;i >=0 ;i--){
            for(int j = i;j < len;j++){
                if(chars[i] == chars[j]){
                    if(j - i <= 1){
                        dp[i][j] = true;
                        result++;
                    }else if(dp[i+1][j-1] == true){
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }
        return result;
    }
}
